#pragma once
#include<iostream>
#include<vector>
using namespace std;

// 闭散列 -- 开地址
//template<class K>
//struct HashFunc
//{
//	size_t operator()(const K& key) { return (size_t)key; }
//};
//
////模板特化
//template<>
//struct HashFunc<string>
//{
//	size_t operator()(const string& key)
//	{
//		size_t hash = 0;
//		for (auto e : key)
//		{
//			hash *= 31;// 降低ASCII相加后的重复率
//			hash += e;
//		}
//		return hash;
//	}
//};
//
//namespace open_address
//{
//	enum State
//	{
//		EMPTY,
//		EXIST,
//		DELETE
//	};
//
//	template<class K, class V>
//	struct HashData
//	{
//		pair<K, V> _kv;
//		State _state = EMPTY;// 开始的状态为空
//	};
//
//	template<class K, class V, class Hash=HashFunc<K>>
//	class HashTable
//	{
//	public:
//		HashTable() { _tables.resize(10); }
//
//		HashData<K, V>* Find(const K& key)
//		{
//			Hash hs;
//			size_t hashi = hs(key) % _tables.size();
//			while (_tables[hashi]._state != EMPTY)
//			{
//				if (_tables[hashi]._state == EXIST 
//					&& _tables[hashi]._kv.first == key)
//					return &_tables[hashi];
//
//				++hashi;
//				hashi %= _tables.size();
//			}
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			HashData<K, V>* ret = Find(key);
//			if (ret == nullptr)
//				return false;
//			else
//			{
//				ret->_state = DELETE;
//				return true;
//			}
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			if (Find(kv.first)) return false;// key不允许冗余
//			//扩容
//			if (_n * 10 / _tables.size() >= 7)
//			{
//				HashTable<K, V, Hash> newHT;
//				newHT._tables.resize(_tables.size() * 2);
//				for (size_t i = 0; i < _tables.size(); i++)
//				{
//					if (_tables[i]._state == EXIST)
//						newHT.Insert(_tables[i]._kv);
//				}
//				_tables.swap(newHT._tables);
//			}
//
//			Hash hs;
//			size_t hashi = hs(kv.first) % _tables.size();
//			while (_tables[hashi]._state == EXIST)
//			{
//				++hashi;
//				hashi %= _tables.size();
//			}
//			_tables[hashi]._kv = kv;
//			_tables[hashi]._state = EXIST;
//			++_n;
//
//			return true;
//		}
//	private:
//		vector<HashData<K, V>> _tables;
//		size_t _n = 0;
//	};
//
//}

// 开散列---hash桶
template<class K>
struct HashFunc
{
	size_t operator()(const K& key) { return (size_t)key; }
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

namespace hash_bucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		Node* Find(const K& key)
		{
			Hash hs;
			size_t hashi = hs(key) % _tables.size();// 算出在表中的位置
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			size_t hashi = key % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
						_tables[hashi] = cur->_next;// 没有前一个直接指向下一个
					else
						prev->_next = cur->_next;

					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		bool Insert(const pair<K, V>& kv)
		{
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();
			if (_n == _tables.size())// 负载到1，进行扩容
			{
				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = hs(cur->_kv.first) % newtables.size();
						cur->_next = newtables[hashi];// 我指向桶的第一个
						newtables[hashi] = cur;// 把桶的第一个给我

						cur = next;
					}
					_tables[i] = nullptr;// 桶的第一个指向空
				}
				_tables.swap(newtables);
			}
			//头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return true;
		}

		HashTable() {  _tables.resize(10, nullptr); }

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};

}


